package com.qfedu.entity.course06;

import java.util.*;

public class Tree<E> {
    TreeNode<E> root;

    /**
     * 递归实现前序遍历
     */
    public List<E> preOrder() {
        List<E> res = new ArrayList<>();
        preOrder(root, res);
        return res;
    }

    private void preOrder(TreeNode<E> root, List<E> res) {
        if (root != null) {
            res.add(root.data);
            preOrder(root.left, res);
            preOrder(root.right, res);
        }
    }

    /**
     * 递归实现中序遍历
     */
    public List<E> inOrder() {
        List<E> res = new ArrayList<>();
        inOrder(root, res);
        return res;
    }

    private void inOrder(TreeNode<E> root, List<E> res) {
        if (root != null) {
            inOrder(root.left, res);
            res.add(root.data);
            inOrder(root.right, res);
        }
    }

    /**
     * 递归实现后序遍历
     */
    public List<E> postOrder() {
        List<E> res = new ArrayList<>();
        postOrder(root, res);
        return res;
    }

    private void postOrder(TreeNode<E> root, List<E> res) {
        if (root != null) {
            postOrder(root.left, res);
            postOrder(root.right, res);
            res.add(root.data);
        }
    }

    /**
     * 非递归实现前序遍历
     */
    public List<E> preOrderNonRecursive() {
        List<E> res = new ArrayList<>();
        Stack<TreeNode<E>> stack = new Stack<>();
        //将根节点入栈
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode<E> cur = stack.pop();
            if (cur != null) {
                //访问当前节点
                res.add(cur.data);
                //将右孩子入栈
                stack.push(cur.right);
                //将左孩子入栈
                stack.push(cur.left);
            }
        }
        return res;
    }

    /**
     * 非递归实现中序遍历
     */
    public List<E> inOrderNonRecursive() {
        List<E> res = new ArrayList<>();
        Stack<TreeNode<E>> stack = new Stack<>();
        TreeNode<E> cur = root;
        while (cur != null || !stack.isEmpty()) {
            //将最左节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.data);
            cur = cur.right;
        }
        return res;
    }

    /**
     * 非递归实现后序遍历 经典写法
     */
    public List<E> postOrderNonRecursive() {
        List<E> res = new ArrayList<>();
        Stack<TreeNode<E>> stack = new Stack<>();
        //当前访问节点
        TreeNode<E> cur = root;
        //上一次访问节点
        TreeNode<E> pre = null;
        while (cur != null || !stack.isEmpty()) {
            //将最左节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            //防止右孩子节点重复遍历
            if (cur.right != null && cur.right != pre) {
                cur = cur.right;
            } else {
                cur = stack.pop();
                res.add(cur.data);
                pre = cur;
                //置空 防止左孩子节点重复入栈
                cur = null;
            }
        }
        return res;
    }

    /**
     * 非递归实现后序遍历（取巧方式，根右左遍历，取反）
     */
    public List<E> postOrderNonRecursive2() {
        List<E> res = new ArrayList<>();
        Stack<TreeNode<E>> stack = new Stack<>();
        //将根节点入栈
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode<E> cur = stack.pop();
            if (cur != null) {
                //访问当前节点
                res.add(cur.data);
                //将左孩子入栈
                stack.push(cur.left);
                //将右孩子入栈
                stack.push(cur.right);
            }
        }
        //列表反转
        Collections.reverse(res);
        return res;
    }

    /**
     * 层序遍历
     */
    public List<E> levelOrder() {
        List<E> res = new ArrayList<>();
        Queue<TreeNode<E>> queue = new LinkedList<>();
        //将根节点入队
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode<E> cur = queue.poll();
            if (cur != null) {
                //访问当前节点
                res.add(cur.data);
                //将左孩子入队
                queue.add(cur.left);
                //将右孩子入队
                queue.add(cur.right);
            }
        }
        return res;
    }
}
